SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Polytree</title>

</head>

Polytree

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a>, and more specifically in <a href="Graph_theory" title="Graph theory">graph theory</a>, a polytree<a href="#cite_note-FOOTNOTEDasgupta1999-1">[1]</a> (also called directed tree,<a href="#cite_note-FOOTNOTEDeo1974206-2">[2]</a> oriented tree<a href="#cite_note-3">[3]</a> or singly connected network<a href="#cite_note-kp83-4">[4]</a>) is a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> whose underlying undirected graph is a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>. In other words, a polytree is formed by assigning an orientation to each edge of a <a href="Connectivity_(graph_theory)" title="Connectivity (graph theory)">connected</a> and <a href="Cycle_(graph_theory)" title="Cycle (graph theory)">acyclic</a> undirected graph.

A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a <a href="Tree_(graph_theory)#Forest" title="Tree (graph theory)">forest</a>. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.

A polytree is an example of an <a href="Orientation_(graph_theory)" title="Orientation (graph theory)">oriented graph</a>.

The term polytree was coined in 1987 by Rebane and <a href="Judea_Pearl" title="Judea Pearl">Pearl</a>.<a href="#cite_note-rp87-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Related_structures">Related structures</h2></div>

<ul><li>An <a href="Arborescence_(graph_theory)" title="Arborescence (graph theory)">arborescence</a> is a directed rooted <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>, i.e. a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> in which there exists a single source node that has a unique path to every other node. Every arborescence is a polytree, but not every polytree is an arborescence.</li>

<li>A <a href="Multitree" title="Multitree">multitree</a> is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a <a href="Multitree" title="Multitree">multitree</a>.</li>

<li>The <a href="Reachability" title="Reachability">reachability</a> relationship among the nodes of a polytree forms a <a href="Partial_order" class="mw-redirect" title="Partial order">partial order</a> that has <a href="Order_dimension" title="Order dimension">order dimension</a> at most three. If the order dimension is three, there must exist a subset of seven elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math><img src="./67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{i}}</annotation>

</semantics>

</math><img src="./5c6e920bac39ad09fff4efef16254595091a1025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.881ex; height:2.009ex;" alt="{\displaystyle z_{i}}" loading="lazy"> (for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=0,1,2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=0,1,2}</annotation>

</semantics>

</math><img src="./709c2513ef1aef141b2ef85e4483a8c3d7ffdc89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.456ex; height:2.509ex;" alt="{\displaystyle i=0,1,2}" loading="lazy">) such that, for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, either <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\leq y_{i}\geq z_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\leq y_{i}\geq z_{i}}</annotation>

</semantics>

</math><img src="./908a6203bbba11356218a7362b7a76bbba838d87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.346ex; height:2.343ex;" alt="{\displaystyle x\leq y_{i}\geq z_{i}}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geq y_{i}\leq z_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geq y_{i}\leq z_{i}}</annotation>

</semantics>

</math><img src="./1e570adfb54e9c750198c8dd45c335e94ebec827.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.346ex; height:2.343ex;" alt="{\displaystyle x\geq y_{i}\leq z_{i}}" loading="lazy">, with these six inequalities defining the polytree structure on these seven elements.<a href="#cite_note-FOOTNOTETrotterMoore1977-6">[6]</a></li>

<li>A <a href="Fence_(mathematics)" title="Fence (mathematics)">fence</a> or zigzag poset is a special case of a polytree in which the underlying tree is a path and the edges have orientations that alternate along the path. The <a href="Reachability" title="Reachability">reachability</a> ordering in a polytree has also been called a generalized fence.<a href="#cite_note-FOOTNOTERuskey1989-7">[7]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Enumeration">Enumeration</h2></div>

The number of distinct polytrees on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> unlabeled nodes, for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1,2,3,\dots }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1,2,3,\dots }</annotation>

</semantics>

</math><img src="./b207567215497887a3250644b8876c23dc3ebf10.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.806ex; height:2.509ex;" alt="{\displaystyle n=1,2,3,\dots }" loading="lazy">, is

/* start https://en.wikipedia.org/ */

.mw-parser-output .block-indent{padding-left:3em;padding-right:0;overflow:hidden}

/* end https://en.wikipedia.org/ */

</style><div class="block-indent" style="padding-left: 1.6em;">1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (sequence <a href="https://oeis.org/A000238" class="extiw external" title="oeis:A000238">A000238</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</div>

<div class="mw-heading mw-heading2"><h2 id="Sumner's_conjecture">Sumner's conjecture</h2></div>

<a href="Sumner's_conjecture" title="Sumner's conjecture">Sumner's conjecture</a>, named after <a href="David_Sumner" title="David Sumner">David Sumner</a>, states that <a href="Tournament_(graph_theory)" title="Tournament (graph theory)">tournaments</a> are <a href="Universal_graph" title="Universal graph">universal graphs</a> for polytrees, in the sense that every tournament with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n-2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n-2}</annotation>

</semantics>

</math><img src="./a8593ff30008d016680ae67c34865b96087b62fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.56ex; height:2.343ex;" alt="{\displaystyle 2n-2}" loading="lazy"> vertices contains every polytree with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.<a href="#cite_note-FOOTNOTEKühnMycroftOsthus2011-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Polytrees have been used as a <a href="Graphical_model" title="Graphical model">graphical model</a> for <a href="Probabilistic_reasoning" class="mw-redirect" title="Probabilistic reasoning">probabilistic reasoning</a>.<a href="#cite_note-FOOTNOTEDasgupta1999-1">[1]</a> If a <a href="Bayesian_network" title="Bayesian network">Bayesian network</a> has the structure of a polytree, then <a href="Belief_propagation" title="Belief propagation">belief propagation</a> may be used to perform inference efficiently on it.<a href="#cite_note-kp83-4">[4]</a><a href="#cite_note-rp87-5">[5]</a>

The <a href="Contour_tree" class="mw-redirect" title="Contour tree">contour tree</a> of a real-valued function on a <a href="Vector_space" title="Vector space">vector space</a> is a polytree that describes the <a href="Level_set" title="Level set">level sets</a> of the function. The nodes of the contour tree are the level sets that pass through a <a href="Critical_point_(mathematics)" title="Critical point (mathematics)">critical point</a> of the function and the edges describe contiguous sets of level sets without a critical point. The orientation of an edge is determined by the comparison between the function values on the corresponding two level sets.<a href="#cite_note-FOOTNOTECarrSnoeyinkAxen2000-9">[9]</a>

<ul><li><a href="Glossary_of_graph_theory" title="Glossary of graph theory">Glossary of graph theory</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-FOOTNOTEDasgupta1999-1">^ <a href="#cite_ref-FOOTNOTEDasgupta1999_1-0">a</a> <a href="#cite_ref-FOOTNOTEDasgupta1999_1-1">b</a> <a href="#CITEREFDasgupta1999">Dasgupta (1999)</a>.

</li>

<li id="cite_note-FOOTNOTEDeo1974206-2"><a href="#cite_ref-FOOTNOTEDeo1974206_2-0">^</a> <a href="#CITEREFDeo1974">Deo (1974)</a>, p. 206.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFHararySumner1980">Harary & Sumner (1980)</a>; <a href="#CITEREFSimion1991">Simion (1991)</a>.

</li>

<li id="cite_note-kp83-4">^ <a href="#cite_ref-kp83_4-0">a</a> <a href="#cite_ref-kp83_4-1">b</a> <a href="#CITEREFKimPearl1983">Kim & Pearl (1983)</a>.

</li>

<li id="cite_note-rp87-5">^ <a href="#cite_ref-rp87_5-0">a</a> <a href="#cite_ref-rp87_5-1">b</a> <a href="#CITEREFRebanePearl1987">Rebane & Pearl (1987)</a>.

</li>

<li id="cite_note-FOOTNOTETrotterMoore1977-6"><a href="#cite_ref-FOOTNOTETrotterMoore1977_6-0">^</a> <a href="#CITEREFTrotterMoore1977">Trotter & Moore (1977)</a>.

</li>

<li id="cite_note-FOOTNOTERuskey1989-7"><a href="#cite_ref-FOOTNOTERuskey1989_7-0">^</a> <a href="#CITEREFRuskey1989">Ruskey (1989)</a>.

</li>

<li id="cite_note-FOOTNOTEKühnMycroftOsthus2011-8"><a href="#cite_ref-FOOTNOTEKühnMycroftOsthus2011_8-0">^</a> <a href="#CITEREFKühnMycroftOsthus2011">Kühn, Mycroft & Osthus (2011)</a>.

</li>

<li id="cite_note-FOOTNOTECarrSnoeyinkAxen2000-9"><a href="#cite_ref-FOOTNOTECarrSnoeyinkAxen2000_9-0">^</a> <a href="#CITEREFCarrSnoeyinkAxen2000">Carr, Snoeyink & Axen (2000)</a>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCarrSnoeyinkAxen2000" class="citation cs2">Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=338659">"Computing contour trees in all dimensions"</a>, Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), Association for Computing Machinery, pp. 918–926, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-453-1</bdi></cite></li>

<li><cite id="CITEREFDasgupta1999" class="citation cs2">Dasgupta, Sanjoy (1999), <a rel="nofollow" class="external text" href="http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf">"Learning polytrees"</a> (PDF), Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999, pp. 134–141</cite>.</li>

<li><cite id="CITEREFDeo1974" class="citation cs2">Deo, Narsingh (1974), <a rel="nofollow" class="external text" href="http://www.edutechlearners.com/download/Graphtheory.pdf">Graph Theory with Applications to Engineering and Computer Science</a> (PDF), Englewood, New Jersey: Prentice-Hall, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-363473-6</bdi></cite>.</li>

<li><cite id="CITEREFHararySumner1980" class="citation cs2"><a href="Frank_Harary" title="Frank Harary">Harary, Frank</a>; <a href="David_Sumner" title="David Sumner">Sumner, David</a> (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0603363">0603363</a></cite>.</li>

<li><cite id="CITEREFKimPearl1983" class="citation cs2">Kim, Jin H.; <a href="Judea_Pearl" title="Judea Pearl">Pearl, Judea</a> (1983), <a rel="nofollow" class="external text" href="http://www.ijcai.org/Proceedings/83-1/Papers/041.pdf">"A computational model for causal and diagnostic reasoning in inference engines"</a> (PDF), Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983, pp. 190–193</cite>.</li>

<li><cite id="CITEREFKühnMycroftOsthus2011" class="citation cs2"><a href="Daniela_K%C3%BChn" title="Daniela Kühn">Kühn, Daniela</a>; Mycroft, Richard; Osthus, Deryk (2011), "A proof of Sumner's universal tournament conjecture for large tournaments", <a href="Proceedings_of_the_London_Mathematical_Society" class="mw-redirect" title="Proceedings of the London Mathematical Society">Proceedings of the London Mathematical Society</a>, Third Series, 102 (4): 731–766, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1010.4430">1010.4430</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fplms%2Fpdq035">10.1112/plms/pdq035</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2793448">2793448</a></cite>.</li>

<li><cite id="CITEREFRebanePearl1987" class="citation cs2">Rebane, George; <a href="Judea_Pearl" title="Judea Pearl">Pearl, Judea</a> (1987), <a rel="nofollow" class="external text" href="http://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf">"The recovery of causal poly-trees from statistical data"</a> (PDF), Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987, pp. 222–228</cite>.</li>

<li><cite id="CITEREFRuskey1989" class="citation cs2"><a href="Frank_Ruskey" title="Frank Ruskey">Ruskey, Frank</a> (1989), "Transposition generation of alternating permutations", <a href="Order_(journal)" title="Order (journal)">Order</a>, 6 (3): 227–233, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00563523">10.1007/BF00563523</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1048093">1048093</a></cite>.</li>

<li><cite id="CITEREFSimion1991" class="citation cs2"><a href="Rodica_Simion" title="Rodica Simion">Simion, Rodica</a> (1991), "Trees with 1-factors and oriented trees", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 88 (1): 93–104, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2891%2990061-6">10.1016/0012-365X(91)90061-6</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1099270">1099270</a></cite>.</li>

<li><cite id="CITEREFTrotterMoore1977" class="citation cs2"><a href="William_T._Trotter" title="William T. Trotter">Trotter, William T. Jr.</a>; Moore, John I. Jr. (1977), "The dimension of planar posets", Journal of Combinatorial Theory, Series B, 22 (1): 54–67, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2877%2990048-X">10.1016/0095-8956(77)90048-X</a></cite>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-20" href="https://en.wikipedia.org/wiki/?title=Polytree&oldid=1301592016">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>